Quantitative estimates on the size of an intersection of sparse automatic sets

Abstract: In this talk, I will talk about use of automata theory in answering problems in number theory. In 1844, Catalan conjectured that the set consisting of natural numbers of the form $2^n+1$, $n \ge 0$ and the set consisting of powers of $3$ has finite intersection. In fact, we can answer such question in more generality, that is, instead of $2$ and $3$, we can show this for $k$ and $\ell$ that are multiplicatively independent (meaning if $k^a=\ell^b$, then $a=b=0$). In automata-theoretic terms, these sets described above are sparse $2$-automatic and sparse $3$-automatic sets, respectively. In fact, a sparse $k$-automatic set can be more complicated than having elements that are of the form $k^n$ or $k^n+1$, and hence, we are answering an even more general question. Moreover, we also prove our result in a multidimensional setting in line with the existing results in the theory of formal languages and finite automata. We show that the intersection of a sparse $k$-automatic subset of $\mathbb{N}^d$ and a sparse $\ell$-automatic subset of $\mathbb{N}^d$ is finite and we give effectively computable upper bounds on the size of the intersection in terms of data from the automata that accept these sets. We will also see how all of this is related to a conjecture of Erdös.

algebraic geometrynumber theory

Audience: researchers in the discipline

SFU NT-AG seminar

Series comments: The Number Theory and Algebraic Geometry (NT-AG) seminar is a research seminar dedicated to topics related to number theory and algebraic geometry hosted by the NT-AG group (Nils Bruin, Imin Chen, Stephen Choi, Katrina Honigs, Nathan Ilten, Marni Mishna).

We acknowledge the support of PIMS, NSERC, and SFU.

For Fall 2025, the organizers are Katrina Honigs and Peter McDonald.

We normally meet in-person in the indicated room. For online editions, we use Zoom and distribute the link through the mailing list. If you wish to be put on the mailing list, please subscribe to ntag-external using lists.sfu.ca